#include<stdio.h>
#include<stdlib.h>

void sort_printf(int t,int *src,int num) //t=0,old;else new
{
	int i;
	char *type;
	if (t==0)
		type="old:";
	else if (t==1)
		type="new:";
	else
		type="last result:";
	printf("%s",type);
	for(i=0;i<num;i++)
		printf("%d,",src[i]);
	printf("\n");
}

void insertion_sort(int a[]) 
{
	int i,j,key;
	for(j=1;j<5;j++)
	{
		sort_printf(1,a,5);
		key=a[j];
		i=j-1;
		while(i>=0 && a[i]> key){
		//	printf("a[i]=%d key=%d\n",a[i],key);
			a[i+1]=a[i];
			i--;
		}
		a[i+1]=key;

	}
		sort_printf(2,a,5);
}

void bubble_sort(int r[])
{
	int i,j,tmp;
	for(i=0;i<4;i++){
		for(j=4;j>i;j--){
			if(r[j]<r[j-1]){
				tmp=r[j];
				r[j]=r[j-1];
				r[j-1]=tmp;
			}
		}
		sort_printf(1,r,5);
	}
		sort_printf(2,r,5);
}

void selection_sort(int r[])
{
printf("********selection sort*******\n");
	int i,j,tmp,min;
	for(i=0;i<4;i++){
		min=i;
		for(j=i+1;j<5;j++)
		{
	//		printf("r[min]=%d,r[j]=%d\n",r[min],r[j]);
			if(r[min]>r[j])
				min=j;
		}
	//	printf("the mininum r[min]=%d\n",r[min]);
			tmp=r[min];
			r[min]=r[i];
			r[i]=tmp;
		sort_printf(1,r,5);
	}
		sort_printf(2,r,5);
}

void merge(int src[], int tmp[], int start, int mid, int end){
	int i=start,j=mid+1,k=start;
	while(i!=mid+1 && j!=end+1)
	{
		if(src[i] >= src[j])
			tmp[k++]=src[j++];
		else
			tmp[k++]=src[i++];
	}
	while(i!=mid+1)
		tmp[k++]=src[i++];
	while(j !=end+1)
		tmp[k++]=src[j++];
	for(i=start;i<=end;i++)
		src[i]=tmp[i];
	sort_printf(1,src,5);
}

void merge_sort(int src[],int tmp[],int start, int end)
{
	int mid;
	if(start < end){
		mid=(start +end)/2;
		merge_sort(src,tmp,start,mid);
		merge_sort(src,tmp,mid+1,end);
		merge(src,tmp,start,mid,end);
	}

}
void quick_sort(int *src, int start, int end)
{
	if(start >= end)
		return ;
	int i=start;
	int j=end;
	int key=src[start];

	while(i<j)
	{
		while(i<j && key <src[j])
			j--;
		src[i]=src[j];
		while(i<j && key >= src[i])
			i++;
		src[j]=src[i];
	}
	src[i]=key;
	quick_sort(src,start,i-1);
	quick_sort(src,i+1,end);
	printf("resut:%d,%d,%d,%d,%d\n",src[0],src[1],src[2],src[3],src[4]);
}

void heapadjust(int *src,int i, int nlen)
{
	int nchild;
	int ntmp;
	for(;2*i+1<nlen;i=nchild){
		nchild=2*i+1;
	//	printf("nchild=%d,(nlen-1)=%d,src[nchild+1]=%d,src[nchild]=%d,src[i]=%d\n",nchild,nlen-1,src[nchild+1],src[nchild],src[i]);
		if((nchild < nlen-1) && (src[nchild+1] >src[nchild]))
			++nchild;
		if(src[i] < src[nchild])
		{
			ntmp=src[i];
			src[i]=src[nchild];
			src[nchild]=ntmp;
		}
		else	break;
	}
	int l;
	for(l=0;l<10;l++)
		printf("%d,",src[l]);
	printf("\n");
}

void heap_sort(int *src,int len)
{
	int i;
	for(i=len/2-1;i>=0;--i)
		heapadjust(src,i,len);
	for(i=len-1;i>0;--i)
	{
		src[i]=src[0]^src[i];
		src[0]=src[0]^src[i];
		src[i]=src[0]^src[i];
		heapadjust(src,0,i);
	}
}

int squ_serch(int *src,int key,int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		if(src[i]==key)
		{
			printf("find it \n");
			return 0;
		}else
			continue;
	}
}

int binary_serch(int *src,int key,int start,int end){
	int mid=-1;
	mid=(start +end)/2;
	if(key==src[mid])
	{
		printf("find it and key=%d\n",src[mid]);
		return mid;
	}
	else if(key < src[mid])
		return binary_serch(src,key,start,mid-1);
	else if(key >src[mid])
		return binary_serch(src,key,mid+1,end);
	return -1;
}

int main(int argc, char **argv)
{
	printf("******bubble sort******\n");
	int a[5]={10,5,2,4,7};
	sort_printf(0,a,5);
	bubble_sort(a);
	printf("********insert sort******\n");
	int b[5]={11,6,3,4,7};
	insertion_sort(b);
	int c[5]={12,5,2,4,7};
	selection_sort(c);
	printf("********merge sort*******\n");
	int d[5]={13,5,1,3,7};
	int e[5];
	sort_printf(0,d,5);
	merge_sort(d,e,0,4);
	sort_printf(2,d,5);
	printf("********quick sort*******\n");
	int quick_a[5]={12,23,5,7,1};
	sort_printf(0,quick_a,5);
	quick_sort(quick_a,0,4);
	sort_printf(2,quick_a,5);
	printf("********heap sort*******\n");
	int h_num[]={9,12,17,30,50,20,60,64,4,49};
	int num=(sizeof(h_num)/sizeof(int));
	printf("num=%d\n",num);
	sort_printf(0,h_num,num);
	heap_sort(h_num,num);
	sort_printf(2,h_num,num);
	printf("********order/squ serch*******\n");
	int sq_a[5]={2,9,1,10,8};
	squ_serch(sq_a,1,5);
	printf("********binary/half serch*******\n");
	int bi_a[5]={3,6,7,11,34};
	int b_r=binary_serch(bi_a,7,0,4);
	printf("b_r=%d\n",b_r);
	printf("********half tree serch*******\n");
return 0;
}
